package main.leetcode.clockin.May;

/**
 * 152.乘积最大子数组
 *
 * <p>给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 * <p>
 *
 * <p>示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
 *
 * <p>示例 2: 输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-product-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day18 {
    public static void main(String[] args) {
        System.out.println(new day18().maxProduct(new int[] {2, 3, -2, 4}));
        System.out.println(new day18().maxProduct(new int[] {-2, 0, -1}));
    }

    public int maxProduct(int[] nums) {
        if (nums.length < 1) {
            return 0;
        }
        // 记录上一轮的最大值
        int max = nums[0];
        // 记录上一轮的最小值
        int min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int num = nums[i];
            if (num >= 0) {
                min = Math.min(num, num * min);
                max = Math.max(num, num * max);
            } else {
                // 防止min被改变
                int tmp = min;
                min = Math.min(num, num * max);
                max = Math.max(num, num * tmp);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}
